package com.cat.dataStructure02;

import java.util.HashMap;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/find-longest-awesome-substring/
 * @create 2025/10/23 12:15
 * @since JDK17
 */

public class Solution49 {
    public int longestAwesome(String s) {
        int n = s.length(), ans = 0, xor = 0;
        char[] arr = s.toCharArray();
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        for (int i = 0; i < n; i++) {
            xor ^= 1 << arr[i] - '0';   // 前缀异或和

            // 有一位可以不相等, 那就改一位试试
            for (int j = 0; j < 31; j++) {
                Integer p = map.getOrDefault(xor ^ (1 << j), i);
                ans = Math.max(ans, i - p);
            }

            if (map.containsKey(xor)) { // 一位都不改，这必然是一个偶数长度的子串
                ans = Math.max(ans, i - map.get(xor) + n % 2);
            } else {
                map.put(xor, i);
            }
        }

        return ans;
    }
}
